package leetcode.level2;

import java.util.Arrays;

/**
 * 240. 搜索二维矩阵 II
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 * @author ben
 * @date 2021-10-25 11:38:22 CST
 */
public class Solution240 {

    public boolean searchMatrix(int[][] matrix, int target) {
        return searchMatrix1(matrix, target);
    }
    
    /**
     * 原始版本
     * @author ben
     * @date 2021-10-25 11:29:52 CST
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
    	int rlen = matrix.length;
    	for (int i=0; i<rlen; i++) {
    		int[] row = matrix[i];
    		int sret = Arrays.binarySearch(row, target);
    		System.out.println("sret=" + sret);
    		if (sret < 0) {
    			continue;
    		} else {
    			return true;
    		}
    	}
    	
    	return false;
    }
    
    /**
     * 入口
     * @author ben
     * @date 2021-10-25 11:38:15 CST
     * @param args
     */
    public static void main(String[] args) {
    	Solution240 s = new Solution240();
    	
    	// 测试数据1
    	int[][] matrix = new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
    	
    	int target = 5;
    	System.out.println("target=" + target);
    	boolean ret = s.searchMatrix(matrix, target);
    	System.out.println("ret=" + ret);
    	
    	target = 31;
    	System.out.println("\ntarget=" + target);
    	ret = s.searchMatrix(matrix, target);
    	System.out.println("ret=" + ret);
	}
    
}
